package demo1;

public class DynamicPlanningPractise {
    /**
     * 乘积最大子数组
     * 时间复杂度O（n）
     * 空间复杂度O（n）*/
    public int maxProduct(int[] nums) {
        int n = nums.length;
        //1 创建dp表
        int[] f = new int[n+1];
        int[] g = new int[n+1];
        //2 初始化
        f[0] = g[0] = 1;
        //3 填表
        int ret = -0x3f3f3f3f;
        for(int i = 1; i <= n; i++) {
            f[i] = Math.max(nums[i-1],Math.max(nums[i-1]*f[i-1],nums[i-1]*g[i-1]));
            g[i] = Math.min(nums[i-1],Math.min(nums[i-1]*f[i-1],nums[i-1]*g[i-1]));
            if(f[i]>ret) ret = f[i];
        }
        //4 返回值
        return ret;
    }

    /**
     * 乘积为正数的最长子数组长度
     * 时间复杂度O（n）
     * 空间复杂度O（n）*/
    public int getMaxLen(int[] nums) {
        int n = nums.length;
        //1 创建dp表
        int[] f = new int[n+1];
        int[] g = new int[n+1];
        //2 初始化 虚拟位置法 -f[0] 与 g[0] 均设置为0
        //3 填表
        int ret = 0;
        for(int i = 1; i <= n; i++) {
            //4 状态转移方程
            if(nums[i-1]==0) {
                f[i] = g[i] = 0;
                continue;
            }
            f[i] = nums[i-1]>0 ? f[i-1]+1 : g[i-1]==0 ? 0 : g[i-1]+1;
            g[i] = nums[i-1]>0 ? g[i-1]==0 ? 0 : g[i-1]+1 : f[i-1]+1;
            if(f[i]>ret) ret = f[i];
        }
        //5 返回值
        return ret;
    }

    /**
     * 等差数列划分
     * 时间复杂度O（n）
     * 时间复杂度O（n）*/
    public int numberOfArithmeticSlices(int[] nums) {
        int n = nums.length;
        //1 创建dp表
        int[] dp = new int[n];
        //2 初始化 --》将dp[0],dp[1]初始化为0，即是不做操作
        //3 填表
        int sum = 0;
        for(int i = 2; i < n; i++) {
            dp[i] = nums[i]-nums[i-1] == nums[i-1]-nums[i-2] ? dp[i-1]+1 : 0;
            sum+=dp[i];
        }
        //4 返回值
        return sum;
    }

}
